// https://www.lintcode.com/problem/longest-harmonious-subsequence/

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: return a integer
     */
    public int findLHS(int[] nums) {
        // write your code here
        // 先排序，最大/最小值之差为1，所以第一个元素定了，后面的值也就限制了。
        int ret = 0;
        int start = 0, new_start = 0;
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; ++i) {
            if ((nums[i] - nums[start]) > 1) { // 超出约束范围
                start = new_start;
            }
            if (nums[i] > nums[i - 1]) { // 下一个子序列可能的开始位置，因为最长，所以相等就排除了。
                new_start = i;
            }
            if ((nums[i] - nums[start]) == 1) {
                ret = Math.max(ret, i - start + 1);
            }
        }
        return ret;
    }
}